#leetcode题目59：螺旋矩阵
#难度：中等
#时间复杂度：O(n^2)
#空间复杂度：O(1)
#方法：矩阵

from typing import List

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:

        if not n:
            return []

        matrix=[[0]*n for _ in range(n)]
        dirs=[(0,1),(1,0),(0,-1),(-1,0)]
        row,col,dirIdx=0,0,0
        for i in range(n*n):
            matrix[row][col]=i+1
            dx,dy=dirs[dirIdx]
            nextRow,nextCol=row+dx,col+dy

            if nextRow<0 or nextRow>n-1 or nextCol<0 or nextCol>n-1 or matrix[nextRow][nextCol]>0:
                dirIdx=(dirIdx+1)%4
                dx,dy=dirs[dirIdx]
            row,col=row+dx,col+dy

            
        return matrix

#测试数据
n=3
#预期输出：[[1,2,3],[8,9,4],[7,6,5]]
solution=Solution()
print(solution.generateMatrix(n))

n=1
#预期输出：[[1]]
solution=Solution()
print(solution.generateMatrix(n))